Week 12 - Countable list and Proof by Induction

In this week's lecture we learn in depth of how which list is countable or not it definition, and how to prove statements using induction and the structure of induction.

When we say that the student numbers in this class is in a list we meat that each of our student number is placed in a one-to-one and on-to list, where it is countable because each one of our student number only appears once and it is labeled in order. This is an example of how a list work and how its counted, where each value in the list refers to a natural number in order to show its position in the list, and how many value is in the list when we want to count it. This implies that Natural numbers is countable due to Naturals are built into the concept of a list, where it shows the position of each Natural number in the list. Further more we can expand this idea to show that not only Natural numbers are countable, but any number that is made up with Natural number is also countable, like Rationals where its n/m (n,m are both Naturals) or a list that is made up with Natural number+2 (skip 2 values each time).

This idea of countable list show that Real numbers is not countable, implies any lists made up of it is also not countable. Cantor's example shows that some Real number is been placed into a list, and by adding 1 to each position of the list we can create a completely new number that doesn't exist in the current list, proving Real number list is not countable.

We can also use Cantor's example to prove that we can't make function in Python where is can predict which function with which input will halt or loop. Due to the amount of function as input and the amount of value is also infinite therefore by Cantor's example when we plug in all the values into a list we can always create a new set of halt or loop output that is unique, implies it is not countable, implies can't compute in Python because Python only works with list that is countable.

from course note chapter 5 pg 6.

we also learned the principle of induction, where again we create a list of each value as input and the output as True or False (Boolean function with Naturals as input because its countable this way). We can basically choose a value where the Base Case for values that produce True in the function and show the induction step to prove the function will produce True for that point on. However we have to be careful on which value we choose as Base Case because values after that cannot produce False or this won't be an induction proof.

Week 11 - Halting Program and Counting Set

This week is a short week because we had a 2 day break on Monday and Tuesday, which implies no class on these days. I felt that the long weekend seems exciting at first but soon after I noticed that the long rest isn't helping my present self. I basically spend the long weekend taking a long break, playing games and go out with friends, it is fun at that instant but for a long run I basically spend a lot of time not doing what I should have done, which is studying for exams and doing assignments.

Back to the topic, on this week's short lecture we were introduced with a few new concepts and the first one is whether a program will halt or not. Halting for a program basically means that if the program will stop doing its computing business and returns the control to the person who is giving the command. It is important to distinguish the difference between a very hard program which takes a long time to run, and a program were its not halting and goes on an infant loop.

It is also very important to know that it is impossible to construct a program that can show whether a program will halt or not because when we tries to write any function that has the magical power of showing the function will halt or not on an input (example like H(f,i) in the picture below) we can basically write down a function called navel_gaze, and by proving that navel_gaze is not commutable  because its contradiction to itself so it implies that the function used in navel
_gaze is also not commutable, proving its impossible to generate a function that knows whether the function will halt or not.

course note chapter 5, pg 8

We also learn in this week's lecture what is the definition of counting. We can count in many ways, referring one-to-one or one-to-many, we can even skip an item while counting. This is why when we say a set is countable we means its counted one-to-one and onto, so that one unique item only refers to another unique item in the set, and there is no item skipped while counting.

Countable sets include anything that is a subset of Natural numbers, Rational numbers is also countable due to it uses Natural numbers as its base (n/m , where n and m is natural numbers) so that we can always refer one Rational number to a Natural number without skipping, thus making it countable. Real numbers not countable because there is infinite amount of numbers you can find in it, and by giving out any of the numbers in between you can prove it not countable by a counter example.

The most important idea we learned in the lecture is where computer programs can only written to be work with sets that are countable lAl<=lNl , and anything that is not countable would be a mismatch in size.

Week 10 - Disproofs and Bounds

In this week's lecture we have learned a lot of different types of proofing involving big-O and big Omega. In Monday's lecture we have learned how to proof big-O statements with direct proof and proving it false by negating the qualifiers and implications in the statement.

Tutorial quiz for this week is easier that the ones I did last week in my opinion, or at least that is what I think maybe because of I have studied and prepared for the quiz more than I did so last week. In this week's tutorial we basally practiced what have we learned in class, with different function and values. Before the quiz I had did the tutorial problem set and solved the big-O proofs in many ways, one is by picking 'c' to be a number, like what Professor Danny did in class, and the second way is pick make the function one power larger and pick 'B' to be a number so 'n' can become what you wanted it to be. (sorry for not been clear, it is pretty hard to explain in words)

All the things we did in Monday's class and tutorial is basically the same concept as in last week's lecture, but starting in Wednesday's class we have started to learn a new type of big-O and Omega proof which is connecting big-O and Omega with implications. This I felt was pretty challenging because it is new and pretty abstract, and does not choose a specific value for 'c' and 'B', but instead it uses the assumptions of the antecedents as resource and pick 'c' and 'B' based on the existing 'c's and 'B's for the antecedent.

Over viewing this week's lecture, what we learned in this week's lecture is basically many different examples consisting of combinations with different functions (polynomial, exponential) and implications with conjunctions and big-O and Omega. In general I felt this week's lecture is pretty challenging, but not that difficult since I have already got general concepts of proving functions.

Week 9 - Counting steps

This week is a hard week because of tutorial quiz on Monday and the term test 2 on Wednesday. In this week's lecture and tutorial we have learned many new things, on how to count steps in a double while loop as well as finding the worst case (big-O) for different quadratic functions.

Usually in the past few weeks tutorial quiz had been very similar to each other on the concept of proving different types of statements. However I felt that in this week's tutorial there has been a significant difficulty jump, because we had to do something new which is counting steps in a double while loop. From last week's lectures I have learned the general idea of counting a single while loop and that's about it, because I had to focus more on studying for term test instead of understanding other new concepts. This is a very fatal mistake and I believe I did very bad on the quiz because I wasn't quite sure what the question is about and how to solve it, thus taking me a lot of time just trying to figure out what is going on for the problem and made me run out of time so I had to write down just what I had in mind at that time.

Example from course note week 9, page 5

In this week's lecture we have learned more examples on how to solve the big-O argument. As you can see from the classic example of finding big-O in the picture above, we can prove this true by finding a B and c to fit the implication with those inequalities.
-The first step on how to solve this is to pick a B and c, just leave a black space on their value so you can fill it in after a few steps.
-The second step is to rewrite f(n) bit by bit so each new one is bigger and more simplified that the old one. Finally into the form of the O(n^2) which is in the form of cn^2.
-Now you can pick the c where it makes cn^2 bigger or equal to the simplified function you got from f(n).
-Fill in the B black by setting a minimum value for n, for example if you were to write '3<=3n' then you must say that n>0 so 3n won't become 0 when n=0.

Week 8 - Wost Case?

In this week's lecture we started an exciting new chapter, which is about worst case. Worst case is the measurement of the complexity of a program. It count on how many steps it takes for a program to be executed. There are two types of worst case, the first is the worst case for a program is by finding the upper bound of the steps the program need for it to be executed, and the second worst case for a program is by finding the lower bound of the steps the program need for it to be executed.

As we can see from the picture below, these two cases can be written using qualifiers and implication:

(From course note chapter 4, slide 3)

Upper bound (big-O) is the worst maximum steps the program needs to be executed. where the exist a c and a B, and by showing that if the B is smaller than n implies the worst case of n is smaller than c*n we can find a function which will be the maximum number of steps it takes for the program to execute.

Lower bound in the other hand is the max minimum steps it takes for the program to execute. The only thing changed between this and the previous statement is that this time B is smaller than n implies the worst case of n is bigger than c*n.

To conclude this week's lesion is that to be honest I personally don't quite fully understand this new concept of big-O at this moment, so I can really say that much, but I think as I get more practice I will get a better understanding of it for sure.

Week 7 - Examples of Proofs

In this week's lecture we learned more proof examples of non-Boolean statements, and how to solve these proofs.

Basically the first step of proofing a statement is to assume the antecedent variables, assume all the variables and indent the next line under the assumption so we know its under the world of the assumption. Then we start to solve the proof by listing the content of the antecedent, and gradually work our way thought the equation making it exactly the same as the consequent. The last part of the proof is close all the assumptions, and conclude the result by taking away the indentation in front of the line.

I have also learned a few additional information in this week's tutorial. Things like we only have to make assumption for the antecedent only if its universal, and if the statement begins with the existential symbol we can go straight to writing down to picking the value for the existential variable so it can derive the function for the proof.

We have also learned examples of indirect proofs, this is where we use the contrapositive of the statement and proofing it true so that the original statement is true.

This week's lecture is pretty challenging despite we had a little rest on today's lecture by doing the exercise sheet 'coin in the drawer'. There is many new concepts of proofing that were introduced this week and most of it can only be mastered by practice, and because of the announcement of assignment 2 in early this week I had to get ready to prove some proofs myself sometimes soon, and I am pretty excited about that.

Week 6 - In depth of proofs

In this week's lecture we learned more examples of proofs. We practiced proofs from for equations to implication to proofs with qualifiers. Due to the Thanks giving holiday at the start of this week, this week's lecture is also very short, but we have learned many quite important types of proofs which made this week's lecture by no means easier than the previous weeks. There are many types of proofs which can mainly categorized into four different proof types, direct proof, contradiction proof, negation proof, case proof.

-Direct proof is the simplest, it is where we proofing by assuming the antecedent is true, and manipulate the antecedent into the form of the consequent, proving the consequent is true. There are also a type of statement called existential, we can prove this statement true simply by proving that there exist one value that satisfies this statement.

-Contradiction proof is another type of direct proof, where we just use the contrapositive of the implication or quantifiers to proof the original statement. Because of the contrapositive is exactly the same as the original statement, we can just simply prove it by following the structure of the direct proof. This types of proof is used when the implication does not give us a clear picture of how to prove it, and by using the contrapositive of the original statement it can show us a much easier way of proving the statement.

-Negation proof is used for proving a false statement. The simplest way of proving that is to negate the statement, and by proving the negated statement true it will show that the original statement is false.

-Case proof is a type of proof where it is best proven using different cases. By using different cases and listing all the possibilities down, it can give us a clear idea of what and how to prove the statement. If the statement has two cases, we prove the statement is true by simply proving both cases are true.